package offerbook;

import java.util.LinkedHashMap;
import java.util.Map;


/**
 * @date 2019/11/10 0010 下午 5:23
 * 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，
 * 第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
 *
 * 分析：如果不是流，固定的String，那么可以遍历，时间O(n²)
 * 是流的话，用一个容器。由于要快速定位，自然想到用Map容器。
 *
 * 如果用HashMap，key是字符，V是出现的次数，有一个问题解决不了，就是流进来的顺序。
 * 所以用LinkedHashMap,key是字符，V是出现的次数，当有char进来，就更新次数。如果第一次进来，则把次数设定为无效。
 * 遍历的时候，是按照插入的顺序遍历的，底层是双向链表。
 * 时空都是O(n)
 *
 *
 *  方式2：自己实现一个容器，让后设定一个字符串记录字符串插入的顺序，找的时候遍历字符串。
 *
 *  测试都通过
 */
public class Code55_FindFirstCharInStringStream {

    private Map<Character,Integer> store = new LinkedHashMap<>();

    //Insert one char from StringStream
    public void Insert1(char ch) {
        if(!store.containsKey(ch)){
            store.put(ch,1);
        }else {
            //已经有了，标志位-1
            store.put(ch,-1);
        }
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce1() {

        //按照插入的顺序遍历即可
        for(Map.Entry<Character,Integer> entry : store.entrySet()){
            if(entry.getValue() == 1){
                return entry.getKey();
            }
        }
        //都没有找到
        return '#';
    }



    //方式2： 自己实现一个容器。字符是256个
    char[] store1 = new char[256];
    //un-thread-safe,底层维护的是一个char数组来存储数据的。扩容长度 newCapacity = (val.length << 1) + 2;
    StringBuilder sb = new StringBuilder();

    //Insert one char from StringStream
    public void Insert(char ch) {
       //统计个数
        store1[ch] += 1;
      //保护原来的顺序
        sb.append(ch);
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        //按照插入的顺序遍历即可
        for (char c : sb.toString().toCharArray()) {
            if(store1[c] == 1){
                return c;
            }
        }
        //都没有找到
        return '#';
    }

}
